// https://www.lintcode.com/problem/search-for-a-range/

public class Solution {
    /**
     * @param A: an integer sorted array
     * @param target: an integer to be inserted
     * @return: a list of length 2, [index1, index2]
     */
    public int[] searchRange(int[] A, int target) {
        // write your code here
        int i = bSearch(A, 0, A.length, target);
        if (i == -1) {
            return new int[]{-1, -1};
        }
        int start = i, end = i;
        while (i != -1) {
            start = i;
            i = bSearch(A, 0, start, target);
        }
        if (end < (A.length - 1)) {
            i = end;
            while ((i != -1) && (i < A.length)) {
                end = i;
                i = bSearch(A, end + 1, A.length, target);
            }
        }
        return new int[]{start, end};
    }
    
    private int bSearch(int[] A, int start, int end, int target) {
        while (start < end) {
            int mid = (start + end) / 2;
            if (A[mid] == target) {
                return mid;
            } else if (A[mid] < target) {
                ++start;
            } else {
                --end;
            }
        }
        return -1;
    }
}